

def insertion_sort(arr):
    n = len(arr)

    # 假设j前面的元素已经排好序
    # 索引j和j-1的元素进行比较，如果小交换
    # 否则退出内层循环 - 优化
    for j in range(1, n):
        # j = 1
        # k = 0
        # j = n - 1
        # k = n-2 到 0
        for k in range(j-1, -1, -1):
            if arr[k+1] < arr[k]:
                arr[k], arr[k+1] = arr[k+1], arr[k]
            else:
                # 没交换直接退出 - 因为j前面已经排好序没必要再比较
                break


if __name__ == '__main__':
    arr = [3, 1, 2, 5, 4]
    insertion_sort(arr)
    print(arr)
    assert arr == [1, 2, 3, 4, 5]